package algorithms.a06unionfind;

import com.google.common.base.Preconditions;

/**
 * 并查集 第二版
 * 通过根进行关联处理,降低unionElements的时间复杂度
 * @author 王昊然
 * @create 2018-02-23 9:13
 **/
public class UnionFind2 {

    private int[] parents;
    private int count;

    public UnionFind2(int n) {
        parents = new int[n];
        count = n;

        for (int i = 0; i < n; i++) {
            parents[i] = i;
        }
    }

    /**
     * 查找p对应的根
     * p是元素下标
     *
     * @param p
     * @return
     */
    public int find(int p) {
        Preconditions.checkArgument(p < count, "p超出集合范围");

        while (p != parents[p]){//如果一个下标的parent值是下标值，那么这是一个根节点
            p = parents[p];
        }
        return p;
    }

    public boolean isConnected(int p, int q) {

        return find(p) == find(q);
    }

    public void unionElements(int p, int q) {

        int rootp = find(p);
        int rootq = find(q);

        if(rootp == rootq) return;

        parents[rootp] = rootq;
    }

    // 测试UF1
    public static void main(String[] args) {

        // 使用10000的数据规模
        int n = 20000;

        // 虽然isConnected只需要O(1)的时间, 但由于union操作需要O(n)的时间
        // 总体测试过程的算法复杂度是O(n^2)的
        UnionFindTestHelper.testUF1(n);
        UnionFindTestHelper.testUF2(n);
    }
}
